from typing import List

# 遇到这种从一个地方像两头增大的，可以找一个点，让其一边增大一遍减小，变成一种二分法

class Solution:

    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:

        # 从左下角开始
        i, j = len(matrix) - 1, 0
        # 没有超出边界的时候
        while i >= 0 and j < len(matrix[0]):
            if matrix[i][j] > target:
                i = i - 1

            elif matrix[i][j] < target:
                j = j + 1

            else:

                return True
            
        return False
    

if __name__ == "__main__":

    a = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]

    target = 25

    sol = Solution()
    res = sol.searchMatrix(a, target)

    print(res)



